Shareware Grab Bag/Shareware Grab Bag.iso/090/public.arc/PKSCRYPT.DOC

Text File | 1985-12-30 | 10KB | 186 lines

           Public Key System for Encryption and Digital Signatures

                       Copyright (c) Lloyd Miller, 1985
                               Calgary, Alberta

Public Key Encryption is a  system of encypting messages where  the encryption
and decryption keys are different. The, so called, public encryption key, used
to encrypt messages  is related to  the private decrption  key but it  is very
difficult to figure  out the decyrption  key if you  only know the  encryption
key.

To send a secret  message to someone you  need to know only  their public key.
For anyone to send you a secret message, you need to let them know your public
key. I have included  my public key with  these files so that  anyone who gets
this system can send me a secret message (I don't know why they might want  to
but they can). If someone  wants me to reply then  they would have to send  me
their public key.

Messages  can  also  be  encrypted  with  the  private  key.  This is called a
signature. Anyone who knows  the public key can  decrypt the message but  only
the  person  who  has  the  corresponding  private  key could have created the
message. I have included a message signed by me in this archive that can  only
be decoded with my private key and  thus could only have been encrypted by  my
private  key.  Signatures  are  not  generally  quite  as useful as the normal
encryption operation but they do have some very interesting capabilities.

Messages can be encrypted more than once. One use for this feature is to  sign
a  secret  message.  To  do  this  you  encrypt  the  message  with  both  the
originator's private key and the recipient's public key. The combination is  a
message which only the recipient can  read and only the originator could  have
created. In order  to read the  message it must  be decrypted twice  using the
recipeint's private key and the  originator's public key in the  reverse order
that it was encrypted.

The difficulty of "breaking"  the key is dependant  on the length of  the keys
used. Keys  of 8  digits (the  smallest ones  supported by  this package)  are
actually quite easy to break.  I havn't really tried it  but a key of even  50
digits is estimated that  it could be decoded  in about 4 hours  using a super
computer and the fastest  factoring algoritm known. A  key of 75 digits  would
take 104 days and a key of 200 digits would take 3,800,000,000 years. For more
on this see the ACM article.

The disadvantage of longer keys is that it takes longer to find and create the
key and the encryption/decryption processes are slower as well. A 8 digit  key
will only take about 1/2 minute  to generate with this software on  a standard
IBM-PC. A 20 digit key takes about 90 sec. A 50 digit key, about 10 min. A 200
digit key will take about 6 to 12 hours. These times may be longer or  shorter
depending on your luck on the random number generator.

GENKEYS is a program  to generate encryption and  decryption keys for the  RSA
(Rivest, Shamir, Adleman) system of public key encryption. See  Communications
of the ACM, February, 1978.

GENKEYS takes, as  the first input  parameter, a single  number from 8  to 200











designating the number  of digits desired  in the key.  This number determines
the level of security of the resulting cypher. It also determins the amount of
time needed to generate a key.

Also input  is a  name for  the key  to be  generated. This  is an 8 character
filename without extention.

Output of the program  is two files. The  first is the public  key file called
keyname.KEY. It  contains two  numbers, each  of which  contains ,at most, the
number of digits requested. The first number is called "n" and is the  product
of two large prime numbers (p and q). The second number is called "e" and is a
number which  is relativly  prime to  (p-1)*(q-1). These  numbers are  the, so
called, public key. This file is the one to be given out and/or published  for
people who want to send you secret messages.

The second file produced is called keyname.KDY. It also has two numbers in it.
The first is  "n" and is  the same as  the "n" in  the public key.  The second
number in this  file is called  "d" and is  the secret decryption  key. "d" is
constructed such that (d * e) MOD ((p -  1) * (q - 1)) = 1. This file  is your
private key for decrypting messages encrypted with your public key and must be
kept secure and private. Perhaps keep it  on a floppy disk and locked up  when
not in use, perhaps with extra copies in separate places.

The key files are only significant up to the end of the second number in  them
so comments may be added at the end of the file. This is particularily usefull
for the public key files where the name and/or address can be added to the key
to  indicate  the  owner  of  the  key.  For  an example of this, see the file
LLOYD.KEY included in this archive. That file is my public key and can be used
to send me secret  messages. When you edit  these files make sure  your editor
does not break any long lines into shorter lines. For instance a 200 digit key
would have over  200 characters in  each of the  first two lines.  These lines
must not be broken up into shorter lines.

One of the nice features of the  RSA key system is that you can  sign messages
by encrypting them with you private key. Such a message can only be  decrypted
with your public key  and thus proves (so  long as you have  kept your private
key secret) that you have originated the message.

Two more programs are included with this system. they are ENCRYPT and DECRYPT.
They use the key files created by GENKEYS to encrypt and decrypt other  files.
The time required for these programs to do their job depends on the length  of
the key used and the size of the file. Any file can be encrypted with any key.
They can only be decrypted with the opposite key of the pair.

ENCRYPT, when run will ask  for the name of the  file to be encrypted and  the
full name of the  key file to be  used for encryption (ie  "LLOYD.KEY"). Third
and last it will ask for a file to store the encrypted file in. ENCRYPT  saves
the name of the key file used to  encrypt in the output file in plain text  so
that the decrypt system can easily figure out which key is needed. It does not
store any keys  in the encrypted  file, just the  key file name.  Encrypt also
saves the  input file  name and  size in  the encyrpted  file. This  is so the
decryption can reproduce the origninal file. The input file name and size  are
encrypted  so  no  extra  information  is  obtainable  from the encrypted file
without the decryption key.












DECRYPT first asks  for name of  the encrypted file.  It reads the  header and
offers you  the default  name for  the decryption  key. (I.E.  if the file was
encrypted with a key called "test.key" it will ask if you want to decrypt with
"test.kdy".) Normally  you would  anser "yes"  to this  question. If  you have
renamed the key file you want to use  then answer no and type in the name  you
want to use. If you  tell the program the wrong  key to use then nothing  will
work right  after that.  DECRYPT then  decodes the  first part  of the file to
obtain the original file name and  size. Once it has decoded this  information
it will ask you if you want to  use the original name for the decoded file  or
you can  enter your  own name  for the  file to  be created. DECRYPT will then
procede to decrypt the rest of the file.


Anyone can make  as many copies  of this software  as they want  and give them
away so long as all three programs and this documentation are included in  any
copies and all files  are in their original  unmodified form. In fact  you are
encouraged to distribute this software  as much as possible by  whatever means
you can  find, electronic,  magnetic, optical  or via  any future technologies
which may be developed. If you find this system usefull then you can encourage
me to write and distribute more of my software by sending $30 to:

    Lloyd Miller
    2420 Capitol Hill Crescent, N.W.
    Calgary, Alberta    T2M-4C2

If you are a corporate or governmental user then the $30 is not optional.

This software  and documentaion  is protected  by copyright  and if  you don't
think that means much then ask a lawyer.

If you  have comments,  complaints (heaven  forbid) or  questions then you can
either send a SASE to the above address or send a message to me via Fidonet(TM
of Tom Jennings) node 134/1, "The Calgary Fido". If you want to send encrypted
messages via  Fidonet then  you will  need your  sysop's co-operation  to send
"attached files". If you want to send encrypted messages via traditional  mail
then you would have to send floppy disks.

This software is  designed to run  on an IBM-PC  using MS-DOS version  2.00 or
later.  I  have  tried  to  avoid  using  any features of the IBM-PC which are
machine dependant so I believe it should work on any system which uses  MS-DOS
or PC-DOS but it has  not been tested on any  other types of systems. I  would
like to hear from  you if you have  tried it on any  other systems and if  you
have had any probelms or not.

These programs are written in Modula-2 using the Logitech Modula-2/86 compiler
system. I would be willing to consider converting these programs for use  with
other Modula-2 systems if anyone wants to pay me to do the convertion. I would
not consider converting the programs to another language. The nature of  these
programs  would  probably  eliminate  from  consideration any M-CODE or P-CODE
interpreter style compiler systems since they would become prohibitivly slow.

                                                                  Lloyd Miller
                                                              1985 December 30